//package 算法模板;
//
//import java.util.Scanner;
//
//public class FastPower {
//
//    // 快速幂方法，计算 a^b % m
//    public static long fastPow(long a, long b, long m) {
//        long result = 1;
//        a = a % m;  // 确保 a 小于 m
//        // a的13次方   将13转为二进制  1101
//        // 2的13次方   1101    1+0+4+8while (b > 0) {
//            // 和1进行取模 判断最后一个是否为1  如果为1对应的权重就是a  需要乘以a
//            if ((b & 1) == 1) {
//                result = (result * a) % m;
//            }
//            // 平方 a，并更新 b
//            a = (a * a) % m;
//            b >>= 1;  // b 右移，相当于 b / 2
//        }
//        return result;
//    }
//
//    public static void main(String[] args) {
//        Scanner sc=new Scanner(System.in);
//        int n=sc.nextInt();
//        long m = 1000000007;
//        while (n-- > 0) {
//            long a=sc.nextLong();
//            long b=sc.nextLong();
//            System.out.println(fastPow(a, b, m));  // 输出 1024
//        }
//    }
//}
